﻿//class Solution
//{
//public:
//	int lengthOfLIS(vector<int>& nums)
//	{
//		int n = nums.size();
//		vector<int> ret;
//		ret.push_back(nums[0]);
//		for (int i = 1; i < n; i++)
//		{
//			if (nums[i] > ret.back()) // 如果能接在最后⼀个元素后⾯，直接放
//			{
//				ret.push_back(nums[i]);
//			}
//			else
//			{
//				// ⼆分插⼊位置
//				int left = 0, right = ret.size() - 1;
//				while (left < right)
//				{
//					int mid = (left + right) >> 1;
//					if (ret[mid] < nums[i]) left = mid + 1;
//					else right = mid;
//				}
//				ret[left] = nums[i]; // 放在 left 位置上
//			}
//		}
//		return ret.size();
//	}
//};